


#include <stdio.h>
#include <stdlib.h>

int just_for_test() {
	printf("Hellow, World!");
	return 0;
}

void swap(int *a, int *b){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void shell_pass(int a[], int n, int d) {
	int i, j;
	for(i=d+1; i<n; i++) {
		if (a[i]<a[i-d]) {
			a[0] = a[i];
			j = i-d;
			do {
				a[j+d] = a[j];
				j -= d;
			} while (j>0 && a[0]<a[j]);
			a[j+d] = a[0];
		} //endif
	}
}

void shell_sort(int a[], int n) {
	int increment[] = {7, 5, 3, 1};
	int i;
	for(i=0; i<4; i++){
		shell_pass(a, n, increment[i]);
	}
}

void straight_selection_sort(int a[], int n){
	// if we will not use a[0] as senetil, we can use temp instead
	int i, j, k;
	for(i=1; i<n; i++){
		k = i;
		for(j=i+1; j<n; j++){
			if(a[k]>a[j]){
				k = j;
			} //endif
		} //endfor
		if(k!=i){
			a[0] = a[i];
			a[i] = a[k];
			a[k] = a[0];
		} //endif
	}
}

void quick_search(int a[], int n){
	int i;
	int count, start, end;
	for(i=0; i<n; i++){
		if(a[i]==0){
			;
		}
	}
}

void heap_fix_down(int a[], int i, int n){
	// This funcion is to adjust the heap from top to bottom from not i
	int tmp, j;
	tmp = a[i];
	j = 2*i+1;
	while(j<n){
		if(j+1<n && a[j]<a[j+1]){
			j++;
		}
		if(tmp>=a[j]){
			break;
		}
		a[(j-1)/2] = a[j];
		j = j*2+1;
	}
	a[(j-1)/2] = tmp;
}

void build_heap(int a[], int n){
	// this function is used to build the heap with a list
	int i;
	for(i=(n-1)/2; i>=0; i--){
		heap_fix_down(a, i, n);
	}
}

void heap_sort(int a[], int n){
	// This function is used for heap sort
	int i;
	int tmp;
	build_heap(a, n);
	for(i=n-1; i>=0; i--){
		swap(&a[i], &a[0]);
		//tmp = a[i];
		//a[i] = a[0];
		//a[0] = tmp;
		heap_fix_down(a, 0, i);
	}
}

/* meger r[low...m] and r[m+1...high] as r[low...high]
 *
 *
*/

void merge(int in[], int out[], int low, int m, int high){
	int i, j, p;
	i = low;
	j = m+1;
	p = low;
	while(i<=m && j<=high)
		out[p++] = (in[i]<in[j]) ? in[i++] : in[j++];
	while(i<=m)
		out[p++] = in[i++];
	while(j<=high)
		out[p++] = in[j++];
}

int test_merge(){
	int in[] = {1,3,5,7,2,4,6,8};
	int size = sizeof(in)/sizeof(int);
	int *out = (int *)malloc(sizeof(int)*size);
	merge(in, out, 0, 3, 7);
	int i;
	for(i=0; i<size; i++)
		printf("%d ", out[i]);
	free(out);
	return 0;
}

/*
 * a pass of merge, will merge n/t of sub-strings with length of t togother
 * n is the length of array
 * t is length of sub-array
 * */
void merge_pass(int in[], int out[], int n, int t){
	int i = 0;
	int j;
	while(n-i>=2*t){ // merge 2 near by seqs with length of t to a seq with length of 2t
		merge(in, out, i, i+t-1, i+2*t-1);
		i = i+2*t;
	}
	if(n-i>t) // there are more than 1 seq (but less than 2 seqs) keys left
		merge(in, out, i, i+t-1, n-1);
	else // there are less than 1 seq keys left
		for(; i<n;i++)
			out[i] = in[i];
}

int test_merge_pass(){
	int in[] = {1,3,5,7,2,4,6,8};
	int size = sizeof(in)/sizeof(int);
	int *out = (int *)malloc(sizeof(int)*size);
	merge_pass(in, out, size, 2);
	int i;
	for(i=0; i<size; i++)
		printf("%d ", out[i]);
	merge_pass(in, out, size, 4);
	for(i=0; i<size; i++)
		printf("%d ", out[i]);
	free(out);
	return 0;
}

/*
 * Merge sort from down to top
 */
int merge_sort(int in[], int size){
	int i = 1;
	int *out = (int *)malloc(sizeof(int)*size);
	if(!out){
		printf("No enough space!");
		return 1;
	}
	while(i<size){
		merge_pass(in, out, size, i);
		i = i*2;
		merge_pass(out, in, size, i);
		i *= 2;
	}
	free(out);
	return 0;
}

void merge_reverse(int in[], int low, int m, int high){
	int i, j, p;
	i = low;
	j = m+1;
	//p = low; //NOTE!!! if we do this like this, the out will ge out index
	p = 0;
	int *out = (int *)malloc(sizeof(int)*(high-low+1));
	while(i<=m && j<=high)
		out[p++] = (in[i]<in[j]) ? in[i++] : in[j++];
	while(i<=m)
		out[p++] = in[i++];
	while(j<=high)
		out[p++] = in[j++];
	for(p=0,i=low; i<=high; p++,i++)
		in[i] = out[p];
	free(out);
}

/*
 * merge sort from top to down, which is a reverse progress.
 * */
void merge_sort_top_to_down(int in[], int low, int high){
	int mid;
	int i = low;
	if(low<high){
		mid = (low+high)/2;
		merge_sort_top_to_down(in, low, mid);
		merge_sort_top_to_down(in, mid+1, high);
		merge_reverse(in, low, mid, high);
	}
}

void test_merge_sort_top_to_down(){
	int in[] = {83, 63, 71, 46, 11, 95, 95, 84, 91, 14};
	merge_sort_top_to_down(in, 0, 9);
	int i;
	for(i=0; i<=9; i++)
		printf("%d ", in[i]);
}
